
//? O(nlog2n) 稳定 空间O(n)
function mergeSort(arr) {
    const len = arr.length;
    //? 当被分割的数组只有一个元素时，返回数组。思想就是分解成N组 然后对每组都排序再合并。
    if (len <= 1) return arr;
    let mid = Math.floor(len / 2)
    //? 分左
    const left = mergeSort(arr.slice(0 ,mid))
    //? 分右
    const right = mergeSort(arr.slice(mid ,len))
    return merge(left ,right)
}
function merge(left,right) {
    let i = 0
    let j = 0
    let res = []
    while (i < left.length && j < right.length) {
        if (left[i] > right[j]) {
            res.push(right[j])
            j ++
        }
        else {
            res.push(left[i])
            i ++
        }
    }

    if (i < left.length) {
        return [...res,...left.slice(i)]
    }
    else {
        return [...res,...right.slice(j)]
    }

}

console.log(mergeSort([4, 2, 8, 0, 5, 7, 1, 3, 9]));
